package leetcode.code1898;

import java.util.HashSet;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int maximumRemovals(String s, String p, int[] removable) {
		char[] cs = s.toCharArray();
		char[] cp = p.toCharArray();
		int l = 0, r = removable.length - 1;
		int ans = -1;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			Set<Integer> hash = new HashSet<>();
			for (int i = 0; i <= mid; i++) {
				hash.add(removable[i]);
			}
			boolean check = this.check(cp, cs, hash);
			if (check) {
				ans = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return ans + 1;

	}

	private boolean check(char[] cp, char[] cs, Set<Integer> hash) {
		int p = 0;
		int c = 0;
		while (p < cp.length && c < cs.length) {
			char cur = cp[p];
			while (c < cs.length && (hash.contains(c) || cs[c] != cur)) {
				c++;
			}
			if (c < cs.length && cs[c] == cur) {
				c++;
				p++;
			}
		}
		return p == cp.length;
	}

	@Override
	public void debug4() {
		H.compare(2, this.maximumRemovals("abcacb", "ab", H.str2array3("[3,1,0]")));
		H.compare(1, this.maximumRemovals("abcbddddd", "abcd", H.str2array3("[3,2,1,4,5,6]")));
		H.compare(0, this.maximumRemovals("abcab", "abc", H.str2array3("[0,1,2,3,4]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
